#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-13 10:04 上午
# @Author  : yangdy
# @File    : 130. 被围绕的区域
# @Software: PyCharmCE
from typing import List


class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board:
            return
        m, n = len(board), len(board[0])
        area, areas = [], []
        la, li = 0, -1
        ss = [[0 for i in range(n)] for j in range(m)]
        step = [(-1, 0), (0, 1), (1, 0), (0, -1)]

        def dfs(x, y):
            if board[x][y] == 'X' or ss[x][y] == 1:
                return
            ss[x][y] = 1
            for si in step:
                xx, yy = x + si[0], y + si[1]
                if 0 <= xx < m and 0 <= yy < n:
                    if board[xx][yy] == 'O' and ss[xx][yy] == 0:
                        area[li].append((xx, yy))
                        areas[li][0] += 1
                        dfs(xx, yy)
                else:
                    areas[li][1] = 1

        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O' and ss[i][j] == 0:
                    area.append([(i, j)])
                    areas.append([1, 0])
                    la, li = la + 1, li + 1
                    dfs(i, j)

        for i in range(la):
            if areas[i][1] == 0:
                for j in range(len(area[i])):
                    board[area[i][j][0]][area[i][j][1]] = 'X'
        return


solve = Solution()

questions = [
    ([['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']],),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    for qii in range(len(q[0])):
        print(' ', q[0][qii])
    print('ans:', solve.solve(q[0]))
    for qii in range(len(q[0])):
        print(' ', q[0][qii])

